package ch9sorting;

import java.util.ArrayList;
import java.util.Collections;

public class Ex7 {
	class HtWt implements Comparable<HtWt>{
		int ht;
		int wt;
		
		public HtWt(int i, int j) {
			ht=i;
			wt=j;
		}

		public boolean isBefore(HtWt item) {
			return (this.ht <= item.ht) && (this.wt <= item.wt);
		}

		@Override
		public int compareTo(HtWt o) {
			if (this.ht < o.ht) {
				return -1;
			}
			else if (this.ht > o.ht){
				return 1;
			}
			else {
				return this.wt - o.wt;
			}
		}
		
		@Override
		public String toString() {
			return "("+ht+", "+wt+")";
		}
	}
	
	ArrayList<HtWt> items = new ArrayList<Ex7.HtWt>();
	ArrayList<HtWt> maxSeq = new ArrayList<Ex7.HtWt>();

	// Returns longer sequence
	ArrayList<HtWt> seqWithMaxLength(ArrayList<HtWt> seq1, ArrayList<HtWt> seq2) {
		return seq1.size() > seq2.size() ? seq1 : seq2;
	}

	// Fills next seq w decreased wts&returns index of 1st unfit item.
	int fillNextSeq(int startFrom, ArrayList<HtWt> seq) {
		int firstUnfitItem = startFrom;
		if (startFrom < items.size()) {
			for (int i = startFrom; i < items.size(); i++) {
				HtWt item = items.get(i);
				HtWt prevItem = i > 0 ? items.get(i - 1) : null;
				if (i == 0 || prevItem.isBefore(item)) {
					seq.add(item);
				} else {
					firstUnfitItem = i;
				}
			}
		}
		return firstUnfitItem;
	}

	// Find the maximum length sequence
	void findMaxSeq() {
		Collections.sort(items);
		int currentUnfit = 0;
		while (currentUnfit < items.size()) {
			ArrayList<HtWt> nextSeq = new ArrayList<HtWt>();
			int nextUnfit = fillNextSeq(currentUnfit, nextSeq);
			maxSeq = seqWithMaxLength(maxSeq, nextSeq);
			if (nextUnfit == currentUnfit)
				break;
			else
				currentUnfit = nextUnfit;
		}
	}
	
	Ex7() {
		items.add(new HtWt(56, 90));  // 0
		items.add(new HtWt(60, 100)); // 1
		items.add(new HtWt(62, 95));  // 2
		items.add(new HtWt(68, 110)); // 3
		items.add(new HtWt(70, 150)); // 4
		items.add(new HtWt(75, 190)); // 5
	}
	
	public static void main(String ... argv) {
		Ex7 ex7 = new Ex7();
		ex7.findMaxSeq();
	}
}